home *** CD-ROM | disk | FTP | other *** search
/ Info-Mac 11 / Info-Mac_XI_Disc_1.cdr_ / Info-Mac XI Disc 1.cdr / Programs / Science & Math / MacEspresso 1.0 / espresso / sparse.c < prev    next >
Encoding:
C/C++ Source or Header  |  1989-02-26  |  3.2 KB  |  138 lines  |  [TEXT/R*ch]
  1. /*
  2.     module: sparse.c
  3.  
  4.     make_sparse is a last-step cleanup to reduce the total number
  5.     of literals in the cover.
  6.  
  7.     This is done by reducing the "sparse" variables (using a modified
  8.     version of irredundant rather than reduce), followed by expanding
  9.     the "dense" variables (using modified version of expand).
  10. */
  11.  
  12. #include "espresso.h"
  13.  
  14. pcover make_sparse(F, D, R)
  15. pcover F, D, R;
  16. {
  17.     cost_t cost, best_cost;
  18.  
  19.     cover_cost(F, &best_cost);
  20.  
  21.     do {
  22.     EXECUTE(F = mv_reduce(F, D), MV_REDUCE_TIME, F, cost);
  23.     if (cost.total == best_cost.total)
  24.         break;
  25.     copy_cost(&cost, &best_cost);
  26.  
  27.     EXECUTE(F = expand(F, R, TRUE), RAISE_IN_TIME, F, cost);
  28.     if (cost.total == best_cost.total)
  29.         break;
  30.     copy_cost(&cost, &best_cost);
  31.     } while (force_irredundant);
  32.  
  33.     return F;
  34. }
  35.  
  36. /*
  37.     mv_reduce -- perform an "optimal" reduction of the variables which
  38.     we desire to be sparse
  39.  
  40.     This could be done using "reduce" and then saving just the desired
  41.     part of the reduction.  Instead, this version uses IRRED to find
  42.     which cubes of an output are redundant.  Note that this gets around
  43.     the cube-ordering problem.
  44.  
  45.     In normal use, it is expected that the cover is irredundant and
  46.     hence no cubes will be reduced to the empty cube (however, this is
  47.     checked for and such cubes will be deleted)
  48. */
  49.  
  50. pcover
  51. mv_reduce(F, D)
  52. pcover F, D;
  53. {
  54.     register int i, var;
  55.     register pcube p, p1, last;
  56.     int index;
  57.     pcover F1, D1;
  58.     pcube *F_cube_table;
  59.  
  60.     /* loop for each multiple-valued variable */
  61.     for(var = 0; var < cube.num_vars; var++) {
  62.  
  63.     if (cube.sparse[var]) {
  64.  
  65.         /* loop for each part of the variable */
  66.         for(i = cube.first_part[var]; i <= cube.last_part[var]; i++) {
  67.  
  68.         /* remember mapping of F1 cubes back to F cubes */
  69.         F_cube_table = ALLOC(pcube, F->count);
  70.  
  71.         /* 'cofactor' against part #i of variable #var */
  72.         F1 = new_cover(F->count);
  73.         foreach_set(F, last, p) {
  74.             if (is_in_set(p, i)) {
  75.             F_cube_table[F1->count] = p;
  76.             p1 = GETSET(F1, F1->count++);
  77.             (void) set_diff(p1, p, cube.var_mask[var]);
  78.             set_insert(p1, i);
  79.             }
  80.         }
  81.  
  82.         /* 'cofactor' against part #i of variable #var */
  83.         /* not really necessary -- just more efficient ? */
  84.         D1 = new_cover(D->count);
  85.         foreach_set(D, last, p) {
  86.             if (is_in_set(p, i)) {
  87.             p1 = GETSET(D1, D1->count++);
  88.             (void) set_diff(p1, p, cube.var_mask[var]);
  89.             set_insert(p1, i);
  90.             }
  91.         }
  92.  
  93.         mark_irredundant(F1, D1);
  94.  
  95.         /* now remove part i from cubes which are redundant */
  96.         index = 0;
  97.         foreach_set(F1, last, p1) {
  98.             if (! TESTP(p1, ACTIVE)) {
  99.             p = F_cube_table[index];
  100.  
  101.             /*   don't reduce a variable which is full
  102.              *   (unless it is the output variable)
  103.              */
  104.             if (var == cube.num_vars-1 ||
  105.                  ! setp_implies(cube.var_mask[var], p)) {
  106.                 set_remove(p, i);
  107.             }
  108.             RESET(p, PRIME);
  109.             }
  110.             index++;
  111.         }
  112.  
  113.         free_cover(F1);
  114.         free_cover(D1);
  115.         FREE(F_cube_table);
  116.         }
  117.     }
  118.     }
  119.  
  120.     /* Check if any cubes disappeared */
  121.     (void) sf_active(F);
  122.     for(var = 0; var < cube.num_vars; var++) {
  123.     if (cube.sparse[var]) {
  124.         foreach_active_set(F, last, p) {
  125.         if (setp_disjoint(p, cube.var_mask[var])) {
  126.             RESET(p, ACTIVE);
  127.             F->active_count--;
  128.         }
  129.         }
  130.     }
  131.     }
  132.  
  133.     if (F->count != F->active_count) {
  134.     F = sf_inactive(F);
  135.     }
  136.     return F;
  137. }
  138.